class Node {
    constructor(key) {
        this.left = null;
        this.right = null;
        this.key = key;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // 插入节点
    insert(key) {
        let newNode = new Node(key);

        if (this.root === null) {
            this.root = newNode;
        } else {
            BinarySearchTree.insertNode(this.root, newNode);
        }
    }

    // 插入辅助函数
    static insertNode(node, newNode) {
        if (node.key > newNode.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                BinarySearchTree.insertNode(node.left, newNode)
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                BinarySearchTree.insertNode(node.right, newNode)
            }
        }
    }

    // 中序遍历(对树进行排序操作)
    inOrderTraverse(fn) {
        BinarySearchTree.inOrderTraverseNode(this.root, fn)
    }

    static inOrderTraverseNode(node, fn) {
        if (node !== null) {
            BinarySearchTree.inOrderTraverseNode(node.left, fn);
            fn(node);
            BinarySearchTree.inOrderTraverseNode(node.right, fn);
        }
    }

    // 先序遍历(打印一个结构化的文档)
    preOrderTraverse(fn) {
        BinarySearchTree.preOrderTraverseNode(this.root, fn);
    }

    static preOrderTraverseNode(node, fn) {
        if (node !== null) {
            fn(node);
            BinarySearchTree.preOrderTraverseNode(node.left, fn);
            BinarySearchTree.preOrderTraverseNode(node.right, fn);
        }
    }

    // 后序遍历(后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小)
    postOrderTraverse(fn) {
        BinarySearchTree.postOrderTraverseNode(this.root, fn);
    }

    static postOrderTraverseNode(node, fn) {
        if (node !== null) {
            BinarySearchTree.postOrderTraverseNode(node.left, fn);
            BinarySearchTree.postOrderTraverseNode(node.right, fn);
            fn(node);
        }
    }

    // 获取二叉树的最小值
    min() {
        return BinarySearchTree.minNode(this.root);
    }

    static minNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    }

    // 获取二叉树的最大值
    max() {
        return BinarySearchTree.maxNode(this.root);
    }

    static maxNode(node) {
        if (node) {
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    }

    // 搜索一个特定的值(判断是否存在)
    search(key) {
        return BinarySearchTree.searchNode(this.root, key);
    }

    static searchNode(node, key) {
        if (node === null) {
            return false;
        }

        if (key < node.key) {

            return BinarySearchTree.searchNode(node.left, key);
        } else if (key > node.key) {

            return BinarySearchTree.searchNode(node.right, key);
        } else {

            return true;
        }
    }

    // 移除一个节点
    remove(key) {
        this.root = BinarySearchTree.removeNode(this.root, key);
    }

    static removeNode(node, key) {
        if (node === null) {
            return null;
        }

        if (key < node.key) {
            node.left = BinarySearchTree.removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = BinarySearchTree.removeNode(node.right, key);
            return node;
        } else {
            // 一个叶节点
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            } else if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }

            let aux = this.min(node.right);
            node.key = aux;
            node.right = BinarySearchTree.removeNode(node.right, aux);
            return node;
        }
    }
}